class LRUCache
{
public:
    LRUCache(int capacity)
    {
        this->m = vector<int>(10005, -1);
        this->t = vector<int>(10005, -1);
        this->step = 0;
        this->size = 0;
        this->capacity = capacity;
    }

    int get(int key)
    {
        if (m[key] != -1)
        {
            q.push({key, step});
            t[key] = step;
            ++step;
        }

        return m[key];
    }

    void put(int key, int value)
    {
        if (m[key] != -1)
        {
            m[key] = value;
            q.push({key, step});
            t[key] = step;
            ++step;
            return;
        }

        if (size < capacity)
        {
            m[key] = value;
            q.push({key, step});
            t[key] = step;
            ++step;
            ++size;
        }
        else
        {
            while (true)
            {
                auto [k, s] = q.front();
                q.pop();
                if (s == t[k])
                {
                    m[k] = -1;
                    t[k] = -1;
                    break;
                }
            }
            m[key] = value;
            q.push({key, step});
            t[key] = step;
            ++step;
        }
    }

private:
    vector<int> m;
    queue<pair<int, int>> q;
    vector<int> t;
    int step;
    int size;
    int capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */